/***
 * 随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准
 * 然后就是比基准小的在左边，比基准大的放到右边，如何放做，就是和基准进行交换，
 * 这样交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，
 * 然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
 */
const quickSort = function (arr) {
    for (let i=0,len=arr.length; i< len; i++){
        for (let j=i+1; j<len; j++){
            if (arr[i] > arr[j]) {
                let list = arr[i]
                arr[i] = arr[j]
                arr[j] = list
            }
        }
    }
    return arr
}

console.log(quickSort([10,10,1,2,4,6,7,89,7,4]))
// [ 1, 2, 4, 4, 6, 7, 7, 10, 10, 89 ]

/***
 * 第一趟排序时将数据分成两部分
 * 一部分比另一部分的所有数据都要小。
 * 然后递归调用，在两边都实行快速排序。
 */

const quickSort2 = function (arr) {
    if(arr.length <=1 ) return arr
    let pivotIndex = Math.floor(arr.length / 2)
    let pivot = arr.splice(pivotIndex, 1)[0]
    let left = []
    let right = []
    for (let i=0, len=arr.length; i<len; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort2(left).concat([pivot], quickSort2(right))
}
console.log(quickSort2([10,10,1,2,4,6,7,89,7,4]))
// [ 1, 2, 4, 4, 6, 7, 7, 10, 10, 89 ]
